package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/12/8 14:22
 */
public class LC689三个无重叠子数组的最大和 {

    public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
//        return slidingWindow(nums, k);
        return dynamicProgramming(nums, k);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
        int k = 2;
        System.out.println(Arrays.toString(maxSumOfThreeSubarrays(nums, k)));
    }

    /**
     * dp[i][j]表示考虑前i个数，凑成j个无重叠子数组时的最大值
     * 状态转移方程式：对于任何一个nums[i]都有两种情况，是否要将它考虑进最优方案；
     * 如果不包含，就已经明确了nums[i]对最优解没有任何影响，问题就转换为考虑前i-1个数，凑成j个无重叠子数组的最大值。此时dp[i][j]=dp[i-1][j]
     * 如果包含，说明j区间[i-k+1, i]都要选，此时的dp[i][j]=dp[i-k][j-1]+nums[i-k+1]+nums[i-k+2]+...+nums[i]
     * （求和部分使用前缀和进行预处理）
     * https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/xiao-song-man-bu-can-kao-da-lao-de-dpxie-9eo5/
     */
    private static int[] dynamicProgramming(int[] nums, int k) {
        int n = nums.length;
        //前缀和预处理，方便得到任意连续区间的和
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + nums[i - 1];
        long[][] dp = new long[n + 1][4];
        for (int i = k; i <= n; i++) {
            for (int j = 1; j < 4; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - k][j - 1] + prefix[i] - prefix[i - k]);
            }
        }
        int[] answer = new int[3];
        int i = n, j = 3, index = 2;
        while (j > 0) {
            //如果不取当前数的时候比取当前数还大，当前的i就需要前移
            if (dp[i - 1][j] >= dp[i - k][j - 1] + prefix[i] - prefix[i - k]) {
                i--;
            } else {
                //取首索引，需要减去k
                i -= k;
                j--;
                answer[index--] = i;
            }
        }
        return answer;
    }

    private static int[] slidingWindow(int[] nums, int k) {
        int[] answer = new int[3];
        //使用三个滑动窗口找出三个无重叠子数组的最大和，max1Index1和max2Index2分别记录窗口1和2的最大和的第一个索引位置
        int sum1 = 0, maxSum1 = 0, sum2 = 0, maxSum12 = 0, sum3 = 0, maxSum123 = 0;
        int max1Index1 = 0, max2Index1 = 0, max2Index2 = 0;
        for (int i = k * 2; i < nums.length; i++) {
            sum1 += nums[i - 2 * k];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i < 3 * k - 1) continue;
            if (sum1 > maxSum1) {
                maxSum1 = sum1;
                max1Index1 = i - 3 * k + 1;
            }
            if (sum2 + maxSum1 > maxSum12) {
                maxSum12 = sum2 + maxSum1;
                max2Index2 = i - 2 * k + 1;
                max2Index1 = max1Index1;
            }
            if (maxSum12 + sum3 > maxSum123) {
                maxSum123 = maxSum12 + sum3;
                answer[0] = max2Index1;
                answer[1] = max2Index2;
                answer[2] = i - k + 1;
            }
            sum1 -= nums[i - 3 * k + 1];
            sum2 -= nums[i - 2 * k + 1];
            sum3 -= nums[i - k + 1];
        }
        return answer;
    }
}
